package 树与图.字典树;

/**
 * 530. 二叉搜索树的最小绝对差
 *
 * 给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
 * 差值是一个正数，其数值等于两值之差的绝对值。
 *
 * 思路：采用递归，比较根节点与左右子树的差值，然后递归比较左右子树，全局取最小值
 *
 * 二叉搜索树（BST）的中序遍历结果是一个升序序列，因此最小绝对差一定出现在相邻节点之间。通过中序遍历，记录前一个节点的值，并在遍历过程中计算当前节点与前驱节点的差值，即可高效找到最小值。
 *
 * 步骤：
 * 中序遍历：按左、根、右的顺序遍历BST，保证访问顺序是升序。
 * 维护前驱节点值：记录前一个访问的节点值 pre，初始为 null。
 * 更新最小差值：每次访问节点时，若 pre 不为空，计算当前节点值与 pre 的差值，更新全局最小值。
 * 遍历完成：最终得到的最小差值即为答案。
 */
public class L_530 {

    private int min=Integer.MAX_VALUE; // 全局变量，记录最小差值
    private Integer pre=null; // 全局变量，记录前一个访问的节点值
    public int getMinimumDifference(TreeNode root) {
        inOrder(root);
        return min;
    }

    // 根据中序遍历的特性，中序遍历二叉搜索树，得到升序序列，然后求相邻节点的最小差值
    private void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        // 遍历左子树
        inOrder(root.left);
        // 比较差值
        if(pre != null){
            min = Math.min(min,root.val-pre);
        }
        // 更新前驱节点
        pre = root.val;
        // 遍历右子树
        inOrder(root.right);
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


}
